package binary_tree.Heap.leetcode;

import java.util.*;

/**
 * @Description: 返回数组中出现频率前 k 高的元素
 * @Author Stark
 * @Date 2022/3/6 17:34
 **/
public class Num347_TopKFreq {
    //内部类,用于存储数字和对应出现的次数
    private class Freq implements Comparable<Freq> {
        private Integer num;
        private Integer times;

        public Freq(Integer num, Integer times) {
            this.num = num;
            this.times = times;
        }

        @Override
        public int compareTo(Freq o) {
            return this.times - o.times;
        }
    }
    public int[] topKFrequent(int[] nums, int k) {
        if(k == 1 && nums.length == 1){
            return nums;
        }
        //用Map统计不同的数出现的次数
        Map<Integer,Integer> map = new HashMap<>();
        for(int i : nums){
            map.put(i,map.getOrDefault(i,0) + 1);
        }
        //使用小堆存储k个出现次数最大的类
        Queue<Freq> queue = new PriorityQueue<>(k);
        for(Map.Entry<Integer,Integer> tmp : map.entrySet()){
            //堆还没有满
            if(queue.size() != k) {
                queue.offer(new Freq(tmp.getKey(), tmp.getValue()));
            }else {
                //次数大于堆顶元素才入堆
                if (tmp.getValue() > queue.peek().times) {
                    queue.poll();
                    queue.offer(new Freq(tmp.getKey(),tmp.getValue()));
                }
            }

        }
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = queue.poll().num;
        }
        return ret;
    }
}
